前端基础系列（三） -- 算法 + 数据结构基础

结构化编程

  1. 一行一行执行
  2. 有条件控制语句 if…else…
  3. 有循环控制语句 while(exp) do…

    伪代码

    流程图

算法

  1. 输入：一个算法必须有零个或以上输入量。
  2. 输出：一个算法应有一个或以上输出量，输出量是算法计算的结果。
  3. 明确性：算法的描述必须无歧义，以保证算法的实际执行结果是精确地 匹配要求或期望，通常要求实际运行结果是确定的。
  4. 有限性：依据图灵的定义，一个算法是能够被任何图灵完备系统模拟的一串运算，而图灵机只有有限个状态、有限个输入符号和有限个转移函数（指令）。而一些定义更规定算法必须在有限个步骤内完成任务。
  5. 有效性：又称可行性。能够实现，算法中描述的操作都是可以通过已经实现的基本运算执行有限次来实现。

数据结构

即数据的结构

哈希（Hash）

键值对： { '键' : '值' } ==> Array / Object

  • 计数排序：计数排序使用一个额外的数组 arr （hash），其中第 i 个元素是待排序数组 Arr 中值等于 i 的元素的个数。然后根据数组 arr 来将 Arr 中的元素排到正确的位置（用到了桶，但是每个桶中只有相同的数字，空间浪费）（所有的桶是Hash，桶里是队列，先进先出）。
    复杂度：n + max
    缺点：

    1. 需要一个哈希表示计数工具。
2. 无法对小数和负数排序

  • 桶排序：将数组分到有限数量的桶里。每个桶再个别排序，此时可以用其他排序方法（所有的桶是Hash，桶里是队列，先进先出）

  • 基数排序：只有十个桶（0 - 9），先排个位，之后十位，依次到最高位（所有的桶是Hash，桶里是队列，先进先出）
    说明：比较排序的极限 n*logN

队列（queue）

  • 特点：先进先出
  • 可以用数组实现

栈（stack）

  • 特点：先进后出
  • 可以用数组实现

链表（Linked List）

  • 是一种线性表，但是并不会按线性的顺序存储数据，而是在每一个节点里存到下一个节点的指针(Pointer)。使用链表结构可以克服数组链表需要预先知道数据大小的缺点，链表结构可以充分利用计算机内存空间，实现灵活的内存动态管理。但是链表失去了数组随机读取的优点，同时链表由于增加了结点的指针域，空间开销比较大

  • 数组无法直接删除中间的一项，但是链表可以，链表是动态数组

  • Hash 实现链表，head 表示第一个 Hash ，所有的 Hash 都是节点（node）

树

  • 是一种抽象数据类型（ADT）或是实作这种抽象数据类型的数据结构，用来模拟具有树状结构性质的数据集合。它是由n（n>0）个有限节点组成一个具有层次关系的集合

  • 特点：

    1. 每个节点有零个或多个子节点
    2. 没有父节点的节点称为根节点
    3. 每一个非根节点有且只有一个父节点
    4. 除了根节点外，每个子节点可以分为多个不相交的子树

  • 术语：

    1. 节点的层次：从根开始定义起，根为第1层，根的子节点为第2层，以此类推；
    2. 深度：对于任意节点n,n的深度为从根到n的唯一路径长，根的深度为0；
    3. 节点的度：一个节点含有的子树的个数称为该节点的度；
    4. 树的度：一棵树中，最大的节点的度称为树的度；
    5. 叶节点或终端节点：度为零的节点；

  • 二叉树（Binary tree）：每个节点最多含有两个子树的树称为二叉树

    1. 二叉树的第 i 层至多拥有2的( i-1 )次幂个节点数

  • 完全二叉树：对于一颗二叉树，假设其深度为d（d>1）。除了第d层外，其它各层的节点数目均已达最大值，且第d层所有节点从左向右连续地紧密排列，这样的二叉树被称为完全二叉树

    1. 在一棵二叉树中，除最后一层外，若其余层都是满的，并且最后一层或者是满的，或者是在右边缺少连续若干节点，则此二叉树为完全二叉树（Complete Binary Tree）

    2. 具有n个节点的完全二叉树的深度为log以2为底n的对数＋1。深度为k的完全二叉树，至少有2的ｋ次幂个节点，至多有2的( k+1 )次幂 - 1个节点

  • 满二叉树：所有叶节点都在最底层的完全二叉树

    1. 一棵深度为k，且有2的( k+1 )次幂 - 1个节点的二叉树，称为满二叉树（Full Binary Tree）

    2. 每一层上的节点数都是最大节点数

说明：用数组存储满二叉树和完全二叉树，用Hash存储其他的树

算法和数据结构结合

  1. 我们要解决一个跟数据相关的问题
  2. 分析这个问题，想出对应的数据结构
  3. 分析数据结构，想出算法
    数据结构和算法是互相依存、不可分开的

分类：

  1. 分治法：把一个问题分区成互相独立的多个部分分别求解的思路。这种求解思路带来的好处之一是便于进行并行计算。前端主要使用分治法

  2. 动态规划法：当问题的整体最优解就是由局部最优解组成的时候，经常采用的一种方法

  3. 贪婪算法：常见的近似求解思路。当问题的整体最优解不是（或无法证明是）由局部最优解组成，且对解的最优性没有要求的时候，可以采用的一种方法

  4. 线性规划法：见词条

  5. 简并法：把一个问题通过逻辑或数学推理，简化成与之等价或者近似的、相对简单的模型，进而求解的方法

排序算法

  • 冒泡排序：它重复地走访过要排序的数列，一次比较两个元素，如果他们的顺序错误就把他们交换过来。走访数列的工作是重复地进行直到没有再需要交换，也就是说该数列已经排序完成。
    这个算法的名字由来是因为越大的元素会经由交换慢慢“浮”到数列的顶端，故名。
  • 选择排序：首先在未排序序列中找到最小（大）元素，存放到排序序列的起始位置，然后，再从剩余未排序元素中继续寻找最小（大）元素，然后放到已排序序列的末尾。以此类推，直到所有元素均排序完毕。
  • 插入排序：通过构建有序序列，对于未排序数据，在已排序序列中从后向前扫描，找到相应位置并插入。插入排序在实现上，通常采用in-place排序（即只需用到的额外空间的排序），因而在从后向前扫描过程中，需要反复把已排序元素逐步向后挪位，为最新元素提供插入空间。
  • 基数排序：将整数按位数切割成不同的数字，然后按每个位数分别比较。将所有待比较数值（正整数）统一为同样的数位长度，数位较短的数前面补零。然后，从最低位开始，依次进行一次排序。这样从最低位排序一直到最高位排序完成以后，数列就变成一个有序序列。
  • 快速排序：快速排序使用分治法（Divide and conquer）策略来把一个序列（list）分为两个子序列（sub-lists）。
    步骤为：
    1. 从数列中挑出一个元素，称为”基准”（pivot），
    2. 重新排序数列，所有比基准值小的元素摆放在基准前面，所有比基准值大的元素摆在基准后面（相同的数可以到任何一边）。在这个分区结束之后，该基准就处于数列的中间位置。这个称为分区（partition）操作。
    3. 递归地（recursively）把小于基准值元素的子数列和大于基准值元素的子数列排序。
      递归到最底部时，数列的大小是零或一，也就是已经排序好了。这个算法一定会结束，因为在每次的迭代（iteration）中，它至少会把一个元素摆到它最后的位置去。